//
// Created by Administrator on 2021/11/12.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class Solution {
public:
    /**
     * dp
     * f(i,j) 表示对于范围[i,j]的确保胜利的最小cost
     * f(i,j) = x + max(f(i,x-1),f(x+1,j))
     * f(i,i) = 0
     * @param n
     * @return
     */
    static int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int i = n - 1; i >= 1; --i) {
            for (int j = i + 1; j <= n; ++j) {
                int minCost = INT_MAX;
                for (int k = i; k < j; ++k) {
                    int cost = k + max(dp[i][k - 1], dp[k + 1][j]); // 取k来分割时的最小cost
                    minCost = min(minCost, cost);  // 可以选择取哪个k，但是不能确定取这个k以后的结果（对错），但是有一个预期来选择最小的cost
                }
                dp[i][j] = minCost;
            }
        }
        return dp[1][n];
    }
};

int main() {
    cout << Solution::getMoneyAmount(5) << endl;
    cout << Solution::getMoneyAmount(10) << endl;
    return 0;
}


